package BinaryTreeLearn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DemoTest {



    /**
     * pre：线序遍历得到的数组
     * in：中序遍历得到的数组
     */
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if(pre.length == 0) {
            return null;
        }

        int root = pre[0];
        TreeNode node = new TreeNode(root);

        //寻找根节点在in中的索引
        int i = 0;
        for( ; i<in.length; ++i) {
            if(in[i] == root) {
                break;
            }
        }

        //建立左子树
        int[] leftIn = Arrays.copyOfRange(in, 0, i);
        int[] leftPre = Arrays.copyOfRange(pre, 1, i+1);
        node.left = reConstructBinaryTree(leftPre, leftIn);

        //建立右子树
        int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);
        int[] rightPre = Arrays.copyOfRange(pre, i+1, pre.length);
        node.right = reConstructBinaryTree(rightPre, rightIn);

        return node;
    }


    public static void main(String[] args) {
        String aPre = "1 2 7 8 12 20 78 88 533 809 2305 1017 2143 2463 2479 1051 1128 1456 2630 1386 1981 2319 2830 111 408 2652 2772 526 898 1031 1875 2160 2760 1939 2741 232 250 953 1464 2849 2859 572 1330 1438 2451 1431 1482 1503 1567 2210 1927 1483 1889 1766 2187 2414 41 145 421 708 1844 1867 435 2115 2845 180 248 1371 1434 368 452 2289 2032 474 1543 1563 1648 1619 55 598 1199 2286 2713 2877 2357 2962 887 949 2109 1153 2812 840 943 1049 2224 1176 1920 1248 2370 1181 2140 26 129 233 565 1053 1795 744 1309 2464 2593 1115 2623 2936 430 903 2207 1504 1808 693 2957 2915 142 189 279 694 1331 1470 2779 349 508 871 1067 1261 1804 1902 609 1860 2829 251 559 692 1919 2192 1583 1425 1874 1610 2626 444 2678 888 1725 2688 93 107 134 1021 1751 202 449 1982 2643 164 881 1442 1955 2409 2995 1868 191 1491 2473 1319 187 538 1288 2337 2870 2725 2918 805 1568 2542 2914 2214 222 348 816 1252 647 1530 1888 2540 2954 1058 1523 2657 2233 2693 2977 42 45 201 285 648 1655 2344 2533 2075 1863 2315 2987 2162 298 316 1929 2329 539 1377 265 854 866 1306 2156 1229 1559 2314 456 514 1412 1767 920 924 2244 2986 81 139 173 319 1780 2376 1235 1744 410 2114 2800 2381 2452 796 2030 320 899 2322 2417 1189 1388 1237 486 2222 2524 108 997 1279 2435 2774 1467 1526 2300 2651 634 1159 2795 2853 2263 2334 2356 2308 73 206 221 928 1392 2499 1446 2270 2564 1917 716 1071 1218 2005 2264 2080 973 1170 1402 1960 308 445 636 874 1054 1398 666 1056 1403 2291 803 1093 1443 1367 1582 1595 2842 1587 484 2549 955 1884 2178 2996 2506 92 106 144 788 2913 2527 2971 2642 2973 683 1537 1925 2662 1255 1937 509 1225 1936 2718 1790 2972 2099 2298 745 780 151 519 1765 1969 2426 2163 1632 1958 244 577 1188 1603 2067 373 2277 550 11 34 67 208 315 835 1308 1461 1572 2265 1740 933 1588 2056 2471 2629 2778 461 763 1840 2238 2867 775 228 263 398 616 1146 2543 2975 2241 432 1108 776 321 549 982 2720 762 2197 2421 480 2033 566 1966 1900 2059 2865 2450 76 458 755 1565 1515 2271 2873 875 1382 1756 2762 1007 1259 1569 243 253 392 2000 1719 2876 350 437 750 1077 1589 552 2961 850 1733 54 90 96 580 641 678 2361 1251 2675 1711 2049 199 220 254 1774 772 2860 2562 380 807 2989 1212 1383 507 892 1641 2501 2763 1463 1907 2732 2776 661 1848 2513 670 1079 1639 2018 2342 2301 2810 112 153 193 197 909 1455 654 277 983 1215 2825 1497 2189 1718 856 2177 1390 1942 2861 2650 131 143 304 743 1232 1465 1871 2636 529 1030 2980 2891 1125 836 1260 2744 2796 1462 1510 1517 2518 19 24 86 135 576 1488 1712 2917 1509 2801 1089 1132 2095 1142 360 439 660 2520 1428 2750 1682 1782 2183 1120 167 276 671 825 2128 864 2466 727 1141 2037 2427 2439 207 267 291 1500 2764 411 584 1387 1474 71 219 553 676 999 1447 2112 2608 1791 2940 2369 1070 1277 2170 2700 1350 2028 2923 2387 1573 2092 2331 1941 369 375 1702 2208 2868 2086 2620 2792 687 748 1527 1736 841 916 1173 2456 1772 870 889 1538 2862 2649 33 60 792 1263 1289 2745 1422 2635 1830 1300 1359 1883 2359 911 1481 1965 2639 2035 1604 113 149 530 2991 972 1068 2602 2247 387 1528 1618 2090 1204 2365 211 626 1291 1499 2846 1027 1048 1337 524 1401 2267 2584 1806 607 1661 2674 100 494 551 575 1533 2252 1541 1825 2841 1271 2179 1915 2531 2673 2966 568 1393 2225 2349 1980 2176 766 1634 2507 2038 853 2006 2489 236 261 303 802 1208 502 848 1103 1551 2419 701 2046 268 822 2837 2751 297 813 2976 1324 496 4 13 15 47 69 147 476 726 1094 2174 1637 1631 1757 2641 306 515 1540 2146 2285 2658 2573 2773 463 1323 1797 2893 1013 1242 117 247 328 446 2577 725 2136 2781 657 2437 2939 370 527 1107 1445 1469 1763 945 1753 2394 2147 2945 1059 1701 2195 1450 101 391 1366 1579 2516 2780 1617 2848 1451 2248 2559 209 364 960 1182 1348 2382 1926 2333 597 1647 2982 1652 1134 346 1956 2981 2304 2558 2330 2484 501 994 1213 1991 1612 2403 2748 46 176 177 390 1347 2340 2416 2257 2373 628 1675 2660 388 723 2053 2104 1496 1670 625 1485 2246 1044 272 336 1627 1750 2017 2571 1738 1811 1036 2134 2226 2698 1322 1327 2441 2027 2434 736 2223 2283 2279 1877 2309 116 273 431 1735 1739 2470 447 849 2461 604 905 1234 2216 2326 1420 2440 1539 951 1109 2897 1505 1865 234 310 569 1057 2022 2771 1113 2003 2084 2383 2807 1346 1996 2598 2969 2502 2364 2647 367 2199 2282 2346 2392 2872 668 2912 714 1139 63 98 185 258 491 858 2574 1150 1673 2168 2701 1026 1110 1649 1723 2288 1880 2408 1614 2253 2560 270 531 2149 588 826 2273 1408 2078 2202 3000 289 571 1078 2258 2294 1692 2151 2360 2578 2366 783 940 2605 1803 2878 1846 2220 2704 2708 1098 1282 1476 1243 2512 2692 162 355 443 585 2083 574 1783 1897 2668 2883 2256 975 979 1656 2465 1893 2379 681 732 1035 1771 2024 1018 1028 2896 1690 204 504 770 1363 1064 2927 2008 314 601 1591 1623 1427 2900 1440 1629 2569 1710 2050 2910 136 241 284 377 653 950 2347 1769 1069 2432 1421 2015 2420 2683 1677 1908 2665 477 891 1584 2211 2475 2595 1136 757 2619 2752 1498 2497 400 442 465 1729 1928 2594 554 846 1630 1852 2553 487 1299 2310 2851 563 1123 2494 793 1023 837 1126 2788 2844 998 1147 1602 1606 2105 1249 1553 2335 160 174 405 470 658 1644 1645 1002 2597 2691 1829 489 592 1097 1436 2117 1578 2468 1978 717 737 961 1394 1083 1285 1361 2275 1600 2834 1987 338 356 993 1298 2034 2821 2462 1006 2072 2956 2970 1166 1389 376 663 1336 1082 1472 591 1407 1514 1818 2221 2756 5 17 87 124 155 500 814 861 2227 2351 1352 1409 1441 561 2500 1152 2085 482 518 1659 2532 2959 2803 1256 1449 2001 2695 2313 768 1489 2856 2885 992 1524 2412 1687 2818 2009 2234 1222 1975 1985 229 256 374 378 1793 1062 1511 2228 2994 1250 2110 2676 334 1133 1191 1525 2787 1258 418 429 1781 2235 2869 2433 2696 423 1743 2217 1293 1914 2171 2907 2132 23 56 70 941 1484 2201 2984 1112 2566 2921 1828 186 948 2424 2405 286 1197 1593 1940 2395 2740 2999 318 344 2386 2515 631 832 1345 644 969 1374 1688 2089 958 1246 1280 2544 2637 1984 2196 2316 1210 65 184 448 1100 1796 1885 2188 2355 1104 1198 2552 2088 867 1837 2389 1922 1974 2144 2714 2278 94 104 739 963 2742 280 1459 1620 1876 224 433 467 1878 582 2592 589 1748 2135 919 1003 2203 10 16 68 84 214 401 2460 1033 1364 808 1636 823 123 259 669 1905 1073 2232 1643 2081 288 656 702 865 1586 937 2802 777 1416 1999 2903 915 2546 335 615 1202 1410 1596 1116 1151 1555 2058 1859 22 172 540 812 1127 1722 2661 926 827 1091 2131 1163 1356 1532 733 771 957 1786 2004 818 1061 1267 2138 1375 1881 1268 2060 226 478 922 2768 1158 1418 1452 630 787 851 536 897 1219 1548 1501 1892 2449 613 2576 1810 66 175 179 213 774 939 2813 1341 1549 2978 260 1000 1087 2908 1032 2535 2974 313 399 751 2928 688 1329 1668 252 522 682 1368 2155 2958 1544 2854 1493 341 395 1074 2036 2280 1597 1616 829 1143 1671 2385 986 2606 2932 1117 1709 75 82 357 460 2023 936 1720 2496 1011 1697 2889 2251 231 859 1005 1642 1646 1700 278 1576 2148 2934 2993 407 619 1052 2175 2789 1265 2281 2585 1419 1853 2191 1792 2184 2670 872 921 2625 2947 1130 2504 3 6 39 51 99 110 125 217 684 971 1194 1301 2968 934 1561 2955 1149 2205 2583 274 904 2611 2397 695 709 2299 789 2633 799 1162 1304 1715 1834 1680 2591 2791 2686 894 1694 148 249 622 639 879 1478 1861 1490 2469 2857 707 2292 2554 1066 2100 896 1122 1708 1957 2631 908 1836 1200 1658 2715 383 1010 1205 1746 2042 2902 2012 1468 1676 1977 2260 516 2130 2478 2909 1580 2041 2491 158 212 403 441 724 749 966 1269 1798 907 2317 754 1156 1207 2477 1754 2107 2935 596 1307 2218 2259 2391 1458 1953 290 981 1303 1415 2443 1696 1870 1724 1909 2121 1779 2268 2021 389 742 1685 2628 2822 1332 1276 1590 2407 2551 2758 230 640 929 1333 1512 2653 1809 1357 2052 2323 2759 675 765 2324 2881 2537 906 337 340 384 1022 2297 2739 2784 790 674 728 1435 2613 758 830 1266 1622 1970 2487 2826 1570 2775 2963 1008 2474 2622 1411 53 85 271 741 767 2145 2804 860 1214 2306 1355 2250 1705 2338 2712 2766 2798 409 520 756 2871 843 2154 517 1101 2588 1899 2517 651 885 1728 2809 1144 2044 2997 105 459 643 1195 1698 1414 1789 1932 2157 2839 645 1020 2734 2806 801 1131 2493 1519 1168 1236 1691 2529 120 215 590 1633 2039 667 2215 611 1340 1971 995 1024 2057 2429 1699 2295 525 605 1667 2442 2717 2209 2272 764 2998 820 1681 2098 2482 74 183 351 394 1244 2320 1102 1762 2828 2743 2824 1628 2730 2307 2855 2438 1520 1666 2182 2269 2287 2719 1534 2045 412 1328 1423 1663 2093 2116 2139 454 821 1316 2769 2400 2735 1095 1369 1817 1864 2076 2684 1349 1432 2884 2729 2627 89 118 242 343 498 2020 1179 1454 2325 1745 956 2805 1164 2634 542 1065 1599 2749 2922 734 2746 976 2951 192 545 562 869 1693 1009 1085 2384 1320 877 883 2534 281 464 1312 1819 2541 2074 2406 426 528 1890 791 680 2068 2530 1238 1615 9 18 49 130 171 1910 1963 2599 2243 2410 2901 2031 2254 2428 2988 2671 2847 521 886 1171 2069 555 1016 1678 1086 1742 1662 137 330 704 1424 2694 2119 2580 556 918 2946 2150 292 578 1165 2363 2556 2327 932 325 1575 2142 599 1257 1495 1898 165 295 339 974 1178 2808 1157 1775 2082 2380 996 1135 2555 1426 2485 1930 967 987 2444 1154 1574 1989 2172 2964 1924 1326 2025 1566 1857 327 436 650 2087 1025 1444 1296 1417 600 952 1119 1689 2048 1080 1672 2879 1376 27 37 48 91 900 2548 1029 473 779 1406 1552 1961 2687 2703 1177 1785 2488 1654 77 706 1060 2091 797 1760 2724 544 1313 1405 1557 1224 1430 2490 2777 80 354 396 785 1721 2071 1379 2706 2528 492 857 371 794 1192 450 1518 2733 127 506 1887 2550 1129 1770 1245 1353 416 419 1038 1741 760 1209 2689 1043 1396 1862 1716 97 157 523 1391 1979 2492 2511 2843 1231 1855 2794 200 720 927 1768 1625 2476 1172 1241 1866 2610 381 475 1787 2572 595 1365 2125 438 1339 2064 2318 1373 1695 2875 2890 2894 2126 2446 1040 2567 2967 2231 30 102 146 269 415 845 1794 2339 2953 1138 2141 2436 991 2122 2483 2173 352 406 1674 2838 1047 1297 2836 2690 659 1508 2181 2823 2646 2655 1076 1901 804 1175 1577 2103 1894 2002 1274 1816 1833 2169 2007 806 1184 1378 2565 2904 1882 876 2284 103 322 705 1788 1903 2827 946 1395 2242 2077 2699 2375 2521 2929 424 1121 624 1850 1262 2164 188 205 541 759 665 1283 2677 729 2425 1773 218 505 730 1239 1487 1869 1777 722 2415 2431 1513 2040 223 2358 798 1072 32 57 122 332 481 1084 1105 1730 2949 2372 2648 382 402 1713 1826 1400 1764 2785 1703 2133 2817 140 557 1516 2731 1302 1835 1800 1935 2979 294 2354 1310 1601 2747 156 203 679 2545 2659 753 811 1118 1321 2898 1380 1657 2525 2614 1841 2736 216 614 1923 2454 782 863 617 914 1096 2799 964 1635 1226 2236 109 121 132 564 1050 1947 385 810 1034 1945 2508 2895 457 1325 2480 800 2557 239 980 1453 1494 1879 2761 2070 2200 1684 2249 2062 275 655 984 2266 2941 2094 1240 2328 1281 2616 2757 14 28 35 50 307 311 610 1216 2938 2129 831 1315 2124 1081 1223 711 839 1221 1014 1776 2563 2568 947 1571 1842 1954 2728 1088 358 420 901 1732 2398 1997 629 1479 479 637 719 912 2079 2029 673 1669 1976 2925 2262 1934 2167 2819 72 296 1778 2051 2886 1944 2276 2710 1962 324 579 606 1988 2153 1598 2180 1471 2293 497 583 2664 1858 2111 2618 195 535 593 817 2161 1362 1621 913 1717 2644 413 2097 2399 2453 2604 537 1686 1950 2430 2864 1912 83 152 238 462 558 1019 2505 2943 662 2612 1891 469 1140 372 422 1820 970 2640 2716 194 302 769 1145 1542 1653 1727 2166 2930 245 451 838 2852 862 425 1706 1838 1972 2402 1562 1747 2603 119 150 618 873 1460 1851 1473 1607 746 1183 1211 847 1174 2697 495 781 1990 1992 2101 1737 1952 923 2102 2186 2371 2570 2586 1161 1521 2960 138 567 691 938 1822 2944 586 1611 1752 2445 1665 2026 2666 309 404 713 1843 1114 2413 1397 2230 361 855 2579 1608 29 36 38 210 466 468 1039 1253 1220 2296 573 1037 672 1186 1758 844 1683 2206 2212 649 1581 1714 2447 1522 1531 1707 1951 141 159 246 293 366 2880 2123 359 712 1921 2321 534 1124 1185 2120 2393 1305 2850 2418 2882 170 196 664 1284 1943 2582 2942 2679 1872 2165 890 1311 2738 2835 2811 910 1399 2348 2422 305 623 1638 1807 1906 786 895 1802 2538 868 1640 2509 1896 225 417 697 1075 2931 1847 2705 1994 2906 2503 455 594 1318 1385 2457 608 1273 2350 1755 2990 2459 2948 731 1731 114 126 166 317 333 1294 1486 2702 1111 1272 2663 1275 2204 1594 2290 635 718 1556 978 2194 1384 1895 163 342 700 2600 2765 510 1660 1160 1799 2043 2061 2815 379 646 2783 2467 1193 1823 2707 1334 1335 2682 237 300 386 513 1360 1545 1839 1854 1155 1343 2377 740 778 880 1187 1679 1448 1233 2754 2547 652 710 1995 2609 977 2667 2874 2401 689 990 2920 2680 2681 1933 1968 2261 2601 2727 2985 323 345 499 1535 2198 2621 2782 603 703 1015 834 942 1439 1506 677 1206 1227 815 1090 2055 1338 2711 21 43 59 128 329 543 2065 2193 2726 2190 2645 2118 2654 532 968 1437 2423 2455 1911 2274 1536 587 773 1063 1092 1247 1502 2615 198 925 1217 1613 1759 2523 2587 1564 1821 2672 2753 935 1651 2536 1106 2950 627 1201 1314 2887 2158 2362 1137 1196 1203 2311 2933 312 434 511 721 1983 2073 2302 1529 2863 2767 1001 1351 1904 2237 2411 483 1358 1815 2332 2495 2905 2019 2343 884 1480 2255 2790 353 638 1973 2992 1099 2054 988 1292 2213 2390 2539 1167 1664 2159 2519 2721 52 58 161 488 1761 2127 2481 2832 2983 965 1433 1190 182 1856 2113 2245 560 819 1457 169 738 824 1812 2096 2892 1354 2368 1986 240 852 1814 2814 1845 2840 2336 1805 1948 2797 61 178 266 633 878 1042 1931 1550 784 1949 2786 1824 2106 2656 2374 181 227 1041 1813 1560 2240 2137 472 2816 1546 761 1254 2152 1477 2831 154 954 1278 1558 1605 2047 1592 2624 2514 2937 1264 1609 2755 2486 283 902 1650 2388 642 1287 2010 25 62 235 287 331 397 1228 2239 2352 696 2561 2888 363 548 2367 570 1429 2448 2303 2581 299 326 485 1055 1801 1492 1918 621 1507 2617 2866 2685 2916 301 440 1169 2926 471 2066 347 427 686 1734 428 546 1370 2833 2965 1290 2011 2472 2793 115 365 453 2632 690 2952 1270 2526 2607 2723 2510 2924 257 393 699 715 1873 1004 2014 842 1938 2396 1148 2709 262 493 503 828 893 1946 2312 1342 1626 1344 1749 31 40 44 64 282 1404 2770 2899 917 620 685 1831 2229 931 2345 362 490 2108 2353 2063 1180 1827 1849 1967 2669 2016 2219 79 95 190 1916 985 581 795 1372 747 1547 512 735 1886 612 1045 632 698 2522 133 882 944 1046 1726 1993 1784 2596 1913 2458 2404 959 2185 2820 2378 2858 1295 1466 1704 1959 2589 2737 2638 2919 168 264 602 930 962 1230 1317 2911 2575 989 1012 2013 1413 255 414 547 833 1381 1554 1624 1286 1585 1832 2590 2722 752 1964 2498 1475 1998 2341";
        String bIn = "2305 809 2463 2143 2479 1017 533 2630 1456 1128 1051 1981 1386 2830 2319 88 2652 408 2772 111 1031 898 526 2760 2160 1875 2741 1939 78 1464 953 2849 2859 250 1330 572 1438 2451 232 2210 1567 1503 1927 1482 1431 1889 1483 2187 1766 2414 20 708 1844 1867 421 2115 435 2845 145 1371 1434 248 180 2289 452 2032 368 1648 1563 1543 474 1619 41 1199 2713 2877 2286 2962 2357 598 2109 949 887 1153 2812 55 1049 2224 943 1920 1176 2370 1248 840 2140 1181 12 1053 1795 565 2593 2464 1309 744 2623 2936 1115 233 2207 903 1504 1808 430 2957 693 2915 129 1331 1470 694 2779 279 871 508 1067 349 1804 1902 1261 189 1860 609 2829 142 2192 1919 692 1583 559 1874 1425 2626 1610 251 2678 444 1725 888 2688 26 1751 1021 134 202 1982 449 2643 107 1955 1442 2995 2409 881 1868 164 2473 1491 191 1319 93 2870 2337 1288 2725 2918 538 2914 2542 1568 2214 805 187 816 1252 348 1888 1530 647 2540 2954 222 2657 1523 2233 1058 2693 2977 8 2533 2344 1655 2075 648 2315 2987 1863 2162 285 316 1929 2329 298 1377 539 201 2156 1306 866 1229 1559 854 2314 265 1767 1412 514 920 456 2244 2986 924 45 2376 1780 319 1235 1744 173 2800 2114 2381 2452 410 2030 796 139 2417 2322 899 1388 1189 1237 320 2524 2222 486 81 2435 2774 1279 1467 997 2300 1526 2651 108 2795 2853 1159 634 2334 2356 2263 2308 42 2499 1392 928 2564 2270 1446 1917 221 1218 2005 2264 1071 2080 716 1170 973 1960 1402 206 874 1398 1054 636 1403 1056 666 2291 445 1093 1443 803 1367 1595 2842 1582 1587 308 2549 484 1884 2178 2996 955 2506 73 2913 788 2971 2527 2973 2642 144 1925 2662 1537 683 1937 1255 106 1936 2718 1225 2972 1790 2099 2298 509 780 745 92 2426 1969 2163 1765 519 1958 1632 151 1188 577 1603 2067 244 2277 373 550 7 1461 1308 2265 1572 1740 835 2056 2471 1588 2629 933 2778 315 1840 2238 763 2867 461 775 208 616 398 2543 2975 1146 2241 263 1108 432 776 228 982 2720 549 762 2197 2421 321 2033 480 1966 566 1900 2865 2059 2450 67 1565 755 1515 2873 2271 458 1382 2762 1756 875 1259 1007 1569 76 392 2000 253 1719 2876 243 1077 750 437 1589 350 2961 552 1733 850 34 678 641 2361 580 2675 1251 1711 2049 96 254 1774 220 2860 772 2562 199 2989 807 380 1383 1212 90 2763 2501 1641 892 2732 1907 1463 2776 507 2513 1848 661 2018 2342 1639 2301 1079 670 2810 54 909 1455 197 654 193 1215 2825 983 2189 1497 1718 277 856 2177 153 1942 2861 1390 2650 112 743 1232 304 1871 1465 2636 143 2980 1030 2891 529 1125 131 2796 2744 1260 1462 1510 836 1517 2518 11 1712 2917 1488 2801 1509 576 1132 2095 1089 1142 135 2520 660 439 2750 1428 1782 1682 2183 360 1120 86 2128 825 671 2466 864 276 1141 727 2037 2439 2427 167 1500 2764 291 267 584 411 207 1387 1474 24 676 2112 2608 1447 2940 1791 999 2369 553 2170 1277 2700 1070 2028 2923 1350 2387 219 2331 2092 1573 1941 71 2208 2868 1702 2086 2620 2792 375 1527 748 1736 687 2456 1173 916 841 1772 369 2862 1538 889 2649 870 19 2745 1289 2635 1422 1830 1263 1300 1883 1359 2359 792 1965 2639 1481 2035 911 1604 60 2991 530 1068 2602 972 2247 149 1618 1528 2090 387 2365 1204 113 1291 1499 2846 626 1048 1337 1027 211 2267 2584 1401 1806 524 1661 2674 607 33 2252 1533 575 1541 1825 2841 551 2179 1271 2673 2531 2966 1915 494 2225 2349 1393 1980 2176 568 2507 1634 2038 766 853 2489 2006 100 303 802 1208 261 848 1551 1103 2419 502 701 2046 236 2837 822 2751 268 2976 813 1324 297 496 2 1094 2174 726 1637 476 1757 1631 2641 147 2146 1540 515 2658 2285 2773 2573 306 1323 2893 1797 463 1013 1242 69 446 2577 328 725 2136 2781 247 2939 2437 657 117 1445 1469 1107 527 1763 370 2394 1753 2147 2945 945 2195 1701 1059 1450 47 2516 2780 1579 1366 2848 1617 391 2248 2559 1451 101 1348 1182 2382 960 2333 1926 364 2982 1647 1652 597 1134 209 2981 1956 2558 2304 2484 2330 346 994 1991 1213 501 2403 1612 2748 15 2340 2416 1347 2373 2257 390 1675 628 2660 177 2053 2104 723 1496 1670 388 1485 2246 625 1044 176 2017 1750 2571 1627 1811 1738 336 2134 2226 2698 1036 2441 1327 1322 2027 2434 272 2283 2223 2279 736 1877 2309 46 1739 1735 2470 431 447 2461 849 273 1234 2216 2326 905 2440 1420 1539 604 2897 1109 1865 1505 951 116 2022 1057 2771 569 2003 1113 2383 2084 2807 310 2969 2598 1996 2502 1346 2647 2364 234 2199 2282 2392 2872 2346 367 2912 668 1139 714 13 2574 858 2701 2168 1673 1150 491 1649 1723 2288 1110 1880 2408 1026 1614 2560 2253 258 2149 531 270 826 2273 588 2078 1408 2202 3000 185 2294 2258 1078 2151 1692 571 2578 2360 2366 289 2605 940 2878 1803 1846 2708 2704 2220 783 1282 1476 1098 1243 2692 2512 98 2083 585 443 2883 2668 1897 1783 2256 574 979 1656 2465 975 1893 2379 355 1035 2024 1771 732 1028 2896 1018 681 1690 162 1363 770 504 2927 1064 2008 204 1623 1591 601 2900 1427 314 2569 1629 1440 1710 2910 2050 63 2347 950 1769 653 1069 2432 377 2683 2420 2015 1421 1677 2665 1908 284 2595 2475 2211 1584 891 1136 477 2752 2619 757 2497 1498 241 1729 1928 2594 465 846 554 1630 2553 1852 442 2310 1299 2851 487 1123 2494 563 793 1023 400 1126 2788 2844 837 1147 1606 2105 1602 998 1553 1249 2335 136 1645 1644 658 470 2691 2597 1002 405 1829 174 1436 2117 1097 592 2468 1578 1978 489 1394 961 1083 1285 737 2275 1361 717 2834 1600 1987 160 1298 993 2821 2034 2462 356 2956 2970 2072 1006 1389 1166 338 1336 663 1472 1082 376 1514 1407 591 2221 2756 1818 4 2227 861 2351 814 1352 1441 1409 500 2500 561 2085 1152 155 2532 2959 1659 2803 518 1256 482 1449 2695 2001 2313 124 2885 2856 1489 768 2412 1524 2818 1687 2234 2009 992 1975 1222 1985 87 1793 378 374 1511 2228 2994 1062 2110 1250 2676 256 1133 334 2787 1525 1191 1258 229 2869 2235 1781 429 2433 2696 418 2217 1743 423 1293 2171 2907 1914 2132 17 2984 2201 1484 941 2921 2566 1112 1828 70 2424 948 2405 186 1197 1593 1940 2395 286 2999 2740 56 2515 2386 344 832 1345 631 969 1688 1374 2089 644 318 2544 1280 2637 1246 2316 2196 1984 958 1210 23 1796 1885 1100 2355 2188 448 2552 1198 1104 2088 184 2389 1837 867 1974 2714 2144 1922 2278 65 739 963 2742 104 1459 280 1620 1876 94 1878 467 433 2592 582 224 2135 1748 589 919 1003 2203 5 2460 401 1364 1033 214 1636 808 823 84 259 1905 669 123 2232 1073 1643 2081 68 1586 865 2802 937 702 1999 1416 777 2903 656 915 2546 288 615 1410 1202 1596 335 1151 1116 2058 1555 1859 16 1722 1127 2661 812 926 540 2131 1091 827 1163 1356 1532 172 1786 957 771 2004 733 1061 2138 1267 1881 1375 818 2060 1268 22 2768 922 1452 1418 1158 478 787 630 851 226 1548 1219 1892 1501 897 2449 536 2576 613 1810 10 939 2813 774 1549 1341 2978 213 1087 2908 1000 1032 260 2974 2535 179 399 751 2928 313 688 1668 1329 175 2155 2958 1368 682 1544 2854 522 1493 252 2036 2280 1074 1616 1597 395 829 2385 1671 1143 341 2606 2932 986 1709 1117 66 2023 460 1720 2496 936 1011 357 2889 1697 2251 82 1005 1646 1642 859 1700 231 1576 278 2993 2934 2148 75 1052 2175 2789 619 2585 2281 1265 2191 1853 1419 1792 2670 2184 407 2947 2625 921 872 2504 1130 1 1194 1301 971 684 2968 217 2955 1561 934 1149 2205 2583 125 274 2611 904 2397 110 2299 709 789 2633 695 1304 1834 1715 1162 1680 2791 2591 2686 799 1694 894 99 879 639 1861 1478 1490 2857 2469 622 2292 2554 707 2100 1066 249 1708 1957 2631 1122 896 1836 908 1200 1658 2715 148 2042 1746 2902 1205 2012 1010 1676 1977 1468 2260 383 2130 2909 2478 516 1580 2041 2491 51 966 1269 749 1798 724 2317 907 441 1207 2477 1156 754 2107 1754 2935 403 2218 2259 1307 2391 596 1953 1458 212 2443 1415 1870 1696 1303 981 2121 1909 1724 2268 1779 2021 290 2628 2822 1685 742 1332 389 1590 1276 2551 2407 2758 158 1512 2653 1333 1809 929 1357 2323 2052 2759 640 2324 2881 765 2537 675 906 230 2297 1022 2739 2784 384 790 340 728 674 2613 1435 337 1970 1622 1266 2487 2826 830 2775 1570 2963 758 2622 2474 1008 1411 39 2145 2804 767 2306 1214 1355 860 2250 741 2766 2712 2338 2798 1705 271 756 2871 520 843 2154 409 2588 1101 2517 1899 517 2809 1728 885 1144 651 2044 2997 85 1698 1195 1414 643 2157 2839 1932 1789 459 1020 2806 2734 645 2493 1131 1519 801 1168 2529 1691 1236 105 2039 1633 590 667 2215 215 1340 1971 611 2057 1024 2429 995 1699 2295 120 1667 2717 2442 605 2209 2272 525 2998 764 820 2098 2482 1681 53 2320 1244 394 2828 1762 2743 2824 1102 2730 1628 2855 2307 2438 351 2182 2269 1666 2287 2719 1520 1534 2045 183 1423 2093 1663 1328 2116 2139 412 2769 1316 821 2400 2735 454 1864 1817 2076 1369 2684 1095 2884 1432 2729 1349 2627 74 2020 498 1179 343 2325 1454 1745 242 2805 956 2634 1164 118 2749 1599 2922 1065 542 2746 734 2951 976 89 1693 869 562 1085 2384 1009 1320 545 2534 883 877 192 2541 1819 1312 464 2406 2074 281 1890 528 791 426 2530 2068 680 1615 1238 6 2599 1963 2410 2901 2243 1910 2428 2254 2988 2031 2671 2847 171 1171 886 2069 521 1016 1678 555 1742 1086 1662 130 2694 1424 704 2580 2119 330 2946 918 556 2150 137 2363 2556 1165 2327 578 932 292 2142 1575 325 599 1257 1495 1898 49 2808 1178 974 1775 2380 2082 1157 339 2555 1135 996 2485 1426 1930 295 2444 987 1989 2172 1574 2964 1154 1924 967 2025 1326 1566 1857 165 2087 650 1025 1444 436 1417 1296 327 952 1119 2048 1689 600 1672 2879 1080 1376 18 2548 900 1029 91 1552 1406 779 1961 2687 2703 473 2488 1785 1177 1654 48 2091 1060 706 2724 1760 797 77 1313 1405 1557 544 2490 1430 2777 1224 37 2071 1721 785 2706 1379 2528 396 857 492 354 794 1192 371 1518 2733 450 80 1887 2550 506 1770 1129 1245 1353 127 1038 1741 419 760 1209 2689 416 1862 1396 1716 1043 27 1979 1391 2492 2843 2511 523 2794 1855 1231 157 927 1768 720 2476 1625 200 1866 1241 1172 2610 97 1787 2572 475 1365 2125 595 381 2318 2064 1339 2890 2875 2894 1695 2446 2126 1373 438 2567 2967 1040 2231 9 1794 2953 2339 845 1138 2141 2436 415 2483 2122 991 2173 269 2838 1674 406 1297 2836 1047 2690 352 2823 2181 1508 2655 2646 659 1901 1076 146 2103 1577 1894 2002 1175 1816 1274 2169 1833 2007 804 1184 2904 2565 1378 1882 806 876 2284 102 1903 1788 2827 705 2242 1395 946 2699 2077 2521 2375 2929 322 1121 424 1850 624 2164 1262 103 541 759 205 1283 2677 665 2425 729 1773 188 1239 730 1869 1487 1777 505 2415 2431 722 1513 2040 218 2358 223 1072 798 30 1105 1084 1730 2949 481 2372 2648 332 402 1826 1713 382 2785 1764 1400 2133 1703 2817 122 1516 2731 557 1835 1302 1935 1800 2979 140 2354 294 2747 1601 1310 57 2659 2545 679 1118 811 1321 753 2898 203 2525 1657 2614 1380 2736 1841 156 1923 2454 614 782 863 216 2799 1096 914 1635 964 1226 617 2236 32 1050 564 1947 132 1034 810 385 2508 1945 2895 121 2480 1325 457 2557 800 109 1879 2761 1494 2200 2070 1453 980 2249 1684 2062 239 2941 2266 984 655 2094 275 2328 1240 2757 2616 1281 3 2938 1216 2129 610 2124 1315 831 1081 1223 311 1221 839 2563 1776 2568 1014 711 1842 1571 2728 1954 947 1088 307 901 2398 1732 1997 420 1479 629 358 2079 912 719 2029 637 479 2925 1976 1669 2262 673 1934 2819 2167 50 2886 2051 1778 2710 2276 1944 1962 296 2153 1988 606 1598 2180 579 1471 2293 324 2664 583 1858 497 2111 2618 72 817 2161 593 1362 1621 535 2644 1717 913 195 2399 2453 2097 2604 413 1686 2430 1950 2864 537 1912 35 2505 1019 2943 558 2612 662 1891 462 469 1140 238 1820 422 970 372 2640 2716 152 1542 1145 769 302 2166 1727 1653 2930 194 2852 838 451 862 245 1838 1972 1706 2402 425 1562 2603 1747 83 1851 1460 873 1473 1607 618 1211 1183 746 847 1174 2697 150 1990 1992 2101 781 1737 1952 495 2371 2186 2102 2586 2570 923 1521 2960 1161 119 938 691 2944 1822 567 1752 1611 2445 586 2666 2026 1665 138 1843 713 1114 2413 404 2230 1397 309 2579 855 361 1608 28 1253 1039 2296 1220 468 1037 573 466 1758 1186 672 2212 2206 1683 844 210 1581 2447 1714 649 1522 1531 1951 1707 38 246 2880 366 293 2123 159 712 359 2321 1921 141 1185 2120 1124 2393 534 2850 1305 2882 2418 36 2582 2942 1943 2679 1284 1872 2165 664 2738 2835 1311 2811 890 1399 910 2348 2422 196 1638 1807 1906 623 1802 895 2538 786 305 1640 2509 868 1896 170 1075 697 2931 417 2705 1847 2906 1994 2503 225 1385 1318 2457 594 1273 2350 608 2990 1755 2459 2948 455 1731 731 29 1486 2702 1294 333 1272 1111 2663 317 2204 1275 2290 1594 166 718 1556 635 2194 978 1384 1895 126 2600 2765 700 342 1660 510 1799 2061 2043 1160 2815 163 2783 646 2467 379 2707 1823 1193 1335 1334 2682 114 1545 1360 1839 1854 513 1155 2377 1343 386 880 1679 1187 778 1448 740 2754 1233 2547 300 2609 1995 710 2667 2874 977 2401 652 2920 990 2681 2680 689 1933 1968 2601 2727 2261 2985 237 1535 2621 2198 2782 499 603 1015 703 345 1439 942 1506 834 323 1227 1206 677 2055 1090 815 2711 1338 14 2193 2726 2065 2190 2645 543 2654 2118 329 2423 2455 1437 1911 2274 968 1536 532 773 587 1247 1092 1063 2615 1502 128 1613 2523 2587 1759 1217 1821 2753 2672 1564 925 2536 1651 935 2950 1106 198 1314 2887 1201 2158 2362 627 1203 1196 1137 2311 2933 59 2073 1983 2302 721 2863 1529 2767 511 1351 2237 1904 1001 2411 434 2495 2332 2905 1815 2019 1358 2343 483 1480 884 2790 2255 312 2992 1973 638 2054 1099 353 1292 2213 2539 2390 988 1167 2159 2519 2721 1664 43 1761 2481 2127 2832 2983 488 1433 965 1190 161 2245 2113 1856 182 819 1457 560 58 1812 824 2096 2892 738 2368 1354 1986 169 1814 2814 852 2840 1845 2336 240 1805 2797 1948 52 878 1042 1931 633 1550 266 2786 1949 784 2656 2106 1824 2374 178 1813 1041 2240 1560 2137 227 2816 472 1546 181 2152 1254 761 1477 2831 61 1558 1605 2047 1278 2624 1592 2937 2514 954 1264 2755 1609 2486 154 1650 2388 902 283 642 1287 2010 21 2352 2239 1228 397 2888 2561 696 331 2367 548 363 2448 1429 2303 570 2581 287 1055 485 1801 326 1492 1918 299 2866 2617 2685 1507 2916 621 235 2926 1169 440 471 2066 301 1734 686 427 1370 2833 546 428 2965 347 2472 2011 1290 2793 62 2632 453 2952 690 365 2607 2723 2526 1270 2924 2510 115 1873 715 699 2014 1004 393 2396 1938 842 2709 1148 257 893 828 503 493 1946 2312 262 1626 1342 1344 1749 25 2770 1404 2899 282 917 64 685 1831 2229 620 2345 931 44 2108 2353 490 2063 362 1827 1180 1967 2669 1849 2219 2016 40 1916 190 985 95 795 1372 581 1547 747 79 1886 735 512 1045 612 2522 698 632 31 1993 1726 1046 1784 2596 944 2458 1913 2404 882 2820 2185 2378 2858 959 1704 1959 1466 2737 2589 1295 2638 2919 133 962 930 1317 1230 2911 602 2575 264 1012 2013 989 1413 168 1381 833 1554 1624 547 1832 1585 2590 2722 1286 414 752 1964 2498 255 1998 1475 2341";

        String [] temPre = aPre.split(" ");
        String [] temIn = bIn.split(" ");

        int[] pre = new int[temPre.length];
        int[] in = new int[temIn.length];

        for(int i =0 ; i< temPre.length;i++){
            pre[i] = Integer.valueOf(temPre[i]);
        }

        for(int i =0 ; i< temIn.length;i++){
            in[i] = Integer.valueOf(temIn[i]);
        }

        TreeNode root =  reConstructBinaryTree(pre, in);
        System.out.println(root);

        DemoTest demo = new DemoTest();
        List<Integer> postOrderList = demo.postOrderBinaryTree(root);
        System.out.println("后序遍历的数组= " + postOrderList);

        Long sum = 0L;
        StringBuilder sf = new StringBuilder("sum=");
        for(int j =0 ; j< postOrderList.size(); j++){
            sf.append((j+1)).append("*").append(postOrderList.get(j)).append("+");

            int tem = (j+1)*postOrderList.get(j);
            System.out.println("第" + j +"个数为=" + postOrderList.get(j) +"****" + (j+1) +"*" +  postOrderList.get(j) + "=" + tem);
            sum = sum + tem;
            System.out.println("第" + j +"次相加后和sum=" + sum);
        }

        System.out.println("sf: " + sf.toString());
        System.out.println("总和sum= " + sum);
    }


    //后序遍历二叉树
    ArrayList<Integer> list = new ArrayList<Integer>();
    public  ArrayList<Integer> postOrderBinaryTree(TreeNode pTreeNode){

        if(pTreeNode!=null){
            postOrderBinaryTree(pTreeNode.left); //先左边
            postOrderBinaryTree(pTreeNode.right); //再右边
            list.add(pTreeNode.val); //再中间
        }else{
            return null;
        }
        return list;
    }



}
